package main

import (
	"container/list"
	"fmt"
)

/*
从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

[
  [3],
  [20,9],
  [15,7]
]
*/

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
	var res [][]int
	if root == nil {
		return res
	}
	queue := list.New()
	queue.PushBack(root)
	h := 1 //从上到下树的高度
	var Arr []int
	for queue.Len() > 0 {
		length := queue.Len() //定义该层树有几个元素
		for i := 0; i < length; i++ {
			node := queue.Remove(queue.Front()).(*TreeNode)
			if node.Left != nil {
				queue.PushBack(node.Left)
			}
			if node.Right != nil {
				queue.PushBack(node.Right)
			}
			Arr = append(Arr, node.Val)
		}
		if h%2 == 1 {
			res = append(res, Arr)
		} else {
			res = append(res, re(Arr))
		}
		h++
		Arr = []int{}
	}
	return res
}

//re 反转数组
func re(n []int) []int {
	for i := 0; i < len(n)/2; i++ {
		n[i], n[len(n)-i-1] = n[len(n)-i-1], n[i]
	}
	return n
}

func main() {
	t := &TreeNode{Val: 1}
	t.Left = &TreeNode{Val: 2}
	t.Right = &TreeNode{Val: 3}
	t.Left.Left = &TreeNode{Val: 4}
	t.Left.Right = &TreeNode{Val: 5}
	t.Right.Left = &TreeNode{Val: 6}
	/*树的形状
	       1
	    /     \
	   2       3
	  / \     /
	 4   5   6             */
	fmt.Println("层次排序:")
	fmt.Println(levelOrder(t))

}
